package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最小高度树
 * 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
 *
 * 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），
 * 其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
 *
 * 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为
 * 最小高度树 。
 *
 * 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
 *
 * 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
 * author: Mr.Du
 * Date: 2023/9/1
 * Time: 10:47
 */
public class FindMinHeightTrees {

    public static void main(String[] args) {
        int[][] edges = {{3,0},{3,1},{3,2},{3,4},{5,4}};
        List<Integer> minHeightTrees = findMinHeightTrees(6, edges);
        System.out.println(minHeightTrees);
    }

    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // 1、构建邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int[] edge : edges) {
            // 无向图，等同于双向图
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // 2、找到所有的叶子节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (graph.get(i).size() == 1) {
                queue.add(i);
            }
        }

        // 3、不断删除叶子节点，直到剩下的节点数小于等于 2 个
        int remainNodeNum = n;
        while (queue.size() > 2) {
            int leaf = queue.poll();
            // 将被删除的叶子节点的邻接节点的度减 1
            int neighbor = graph.get(leaf).get(0);
            queue.remove(leaf);
            graph.get(neighbor).remove(Integer.valueOf(leaf));
            // 如果邻接节点的度为 1，说明它也变成了叶子节点
            if (graph.get(neighbor).size() == 1) {
                queue.add(neighbor);
            }
        }

        // 最后剩下的节点就是根节点
        return new ArrayList<>(queue);
    }
}
